Spanning trees, flows, harmonic functions and symmetries of graphs
ABSTRACT

The well-known matrix-tree theorem relates the number of spanning trees 
of a graph X and the Laplace matrix L(X) of X. In fact, there is a more 
deep relation, the spanning trees can be viewed as elements of an 
abelian group Jac(X), called the Jacobian of X, associated with any
connected graph $X$. The size |Jac(X)| is equal exactly to the number of 
spanning trees of X. The Jacobian is standardly defined as a quotient of 
a free abelian group of integer valued functions from V(X) to Z
by a set of harmonic-like identies, relating the graph Jacobian to its 
counterpart in complex analysis. In my talk we present an alternative 
definition of a Jacobian through integer flows satisfying both Kirchhoff 
laws. In each concrete case to compute the Jacobian requires to 
transform the matrix associated to a certain defining system of linear 
equations over the ring of integers into the canonical Smith form. The 
problem is to find the Jacobian for some well-defined (infinite) 
parametrised families of graphs. In particular, computer-based 
experiments show that Jacobian of a random graph is cyclic,
while known results for $K_n$, $K_m,n$ cubes and others have the 
Jacobians of rank >1. We partially explain this phenomenon, by showing 
that the rank of Jacobian is related to the automorphism group of X. 
Behind our research is a general problem of finding combinatorial
interpretations of some algebraic invariants associated to a graph. New 
results presented in the talk were done in collaboration with A. Mednykh 
(Univ. Novosibirsk).